Computer networks are pervasive these days. In a typical computer network, various devices of different types are interconnected via switching elements, such as routers, switches and hubs, to allow the devices to communicate among one another according to a predefined communication model.
There are various ways in which networks can be configured into topologies required by applications on those networks. The simplest network tends to involve hardwiring the various devices together using appropriate switching elements and interconnecting media (e.g., conductive cables, fiber optic cables, the wireless medium, etc.). Although the hardwire approach works well for relatively small, static network configurations, it does not scale well and tends to result in networks that are difficult to manage and upgrade.
Recently, there has been proposed a more flexible approach to building computer networks. Instead of constructing each network topology piecemeal by hardwiring the devices together, the devices are viewed as belonging to a common pool of resources, which are disposed in a hierarchical tree topology. A hierarchical tree topology is selected since devices in the tree communicate among themselves along deterministic communication paths, thereby simplifying the provisioning and upgrade tasks. Within the hierarchical tree topology, the devices are interconnected using a pool of switching elements. Depending on how the switching elements are configured, various logical networks can be constructed from this common pool of devices and switching elements (e.g., switches, routers, and hubs) using, for example, a virtual local area network (VLAN) technology. A discussion of one exemplary VLAN technology may be obtained from the IEEE 802.1Q working group (http://grouper.ieee.org/groups/802/1/,September 2002)
Under this approach, any number of logical network topologies can be constructed simultaneously from the physical network if there are sufficient resources in the common pool of devices and switching elements (e.g., switches, routers, and hubs) of the tree. For example, an organization wishes to create or upgrade to a three-tier application topology having two database servers, five application servers, four web servers, and a firewall for Internet access. From this specification and the communication model, which governs the communication policy (including the expected bandwidth usage) for each device required for the application, the necessary devices (e.g., database servers, application servers, web servers and firewalls) may be picked from the common pool of devices and interconnected using the switching elements in the tree. Thus, the construction of a logical network topology becomes an exercise in picking the required devices from the pool of available devices existing in the tree hierarchy and to configure the switching elements appropriately to interconnect the devices as specified by the communication model and the logical specification. Such a network (containing a variety of devices and network elements so that they comply with a given communication model) is herein referred to as a “farm.”
To facilitate discussion, FIG. 1 illustrates an exemplary data center 100, representing the common pool of networked devices and switching elements from which various farms can be constructed. Data center 100 includes a hub 1101 (containing 8 network ports for a total of 4096 Mbps bandwidth) at the root level of the hierarchical tree. Hub 1101 is coupled with two routers 2000 and 2001, both of which are 8-port, 4096 Mbps routers disposed at level 1 of the tree. Router 2000 is coupled with three switches (8002, 8001, and 8003) and three load balancers (20001, 20002, and 20003), all of which are disposed at level 2 of the tree. Router 2001 is coupled with three switches (9002, 9001, and 9003) and two load balancers (20004 and 20005), all of which are disposed at level 2 of the tree.
Switch 8002, which is a 12-port, 1024 Mbps switch, is coupled to two network attached storage (NAS) devices 24002 and 24003, each of which is a 2-port, 80 Mbps NAS and is disposed at level 3 of the tree. Switch 8002 is also coupled to four LP2000R application servers (numbered 11001, 11002, 11003, and 11004, which are 1-port, 100 Mbps each in the example of FIG. 1), all of which are disposed at level 3 of the tree. Switch 8001, which is a 9-port, 1024 Mbps switch, is coupled to two firewalls 18002 and 19002, each of which is a 2-port, 100 Mbps firewall, as well as four database servers A500 (numbered 12001, 12002, 12003, and 12004, each of which is a 1-port, 100 Mbps server in the example of FIG. 1). Switch 8003, which is a 6-port, 1024 Mbps switch, is coupled to four N4000 application servers (numbered 31001, 31002, 31003, and 31004, each of which is a 1-port, 100 Mbps server).
Switch 9001, which is an 8-port, 1024 Mbps switch, is coupled to a firewall 18003 (2-port, 100 Mbps) as well as four LP2000R (1-port, 100 Mbps) application servers 11005, 11006, 11007, and 11008, all of which are disposed at level 3 of the tree. Switch 9002, which is an 8-port, 1024 Mbps switch, is coupled to a firewall 18004 (2-port, 100 Mbps) and five LP2000R (1-port, 100 Mbps) application servers 11010, 11011, 11012, 11013, and 11014, all of which are disposed at level 3 of the tree. Switch 9003, which is a 11-port, 1024 Mbps switch, is coupled to two firewalls 18005 and 18006 (2-port, 100 Mbps each) and two LP2000R (1-port, 100 Mbps) application servers 11014 and 11015. Switch 9003 is also coupled with four database servers A500 (1-port, 100 Mbps each and numbered 12005, 12006, 12007, and 12008 in the example of FIG. 1), all of which are disposed at level 3 of the tree.
Suppose one wishes to build a farm, which specifies a three-tier architecture having two A500 database servers, five LP2000R application servers, and a firewall for Internet access, from the physical network specified in the data center 100 of FIG. 1. Furthermore, the LP2000R application servers do not communicate among one another, nor do the A500 database servers communicate between themselves. The logical specification of this farm is shown in FIG. 2. Assuming all the devices in data center 100 are available for use, there are more than sufficient resources in data center 100 to construct the farm.
If efficiency is not a concern, the farm may be constructed by randomly picking the devices (e.g., the database servers, the LP2000R application servers, and the firewall) from the available devices in the data center 100, and appropriately configuring the switching elements that are disposed along their possible communication paths to construct the required farm. However, such a random approach does not optimize the bandwidth usage in data center 100 and may require data to traverse more hops than necessary. Consider the communication between the firewall and an LP2000R application server, for example. If firewall 18002 and LP2000R application server 11001 are picked, the communication between firewall 18002 and LP2000R application server 11001 requires only four hops (via switch 8001, router 2000, and switch 8002). On the other hand, if firewall 18002 and LP2000R application server 11005 are picked, the communication between firewall 18002 and LP2000R application server 11005 requires a total of six hops (via switch 8001, router 2000, hub 1101, router 2001, and switch 9001). In addition, traffic congestion can become a problem at the switches. For example, if all devices connected to router 2000 send all their traffic (4632 Mbps) though it, router 2000 will become congested because it only has 4096 Mbps available, and traffic will be dropped at the router. The random approach does not take bandwidth efficiency and network congestion into consideration when picking the constituent devices.
Another approach known as first-come-first-served (FCFS) dictates that one may traverse the tree in a given direction and gather as many resources along the way as possible until all resource requirements are satisfied. Under this approach, the aforementioned farm may be constructed, for example, using resources encountered when traversing through router 2000, its child nodes and its grandchild nodes, and then through router 2001, its child nodes and its grandchild nodes, stopping along the way if and when the required resources are all obtained. In this example, the first firewall encountered is firewall 18002, the first two database servers encountered are A500 database servers 12001 and 12002, and the five LP2000R application servers encountered are LP2000R servers 11001, 11002, 11003, 11004, and 10005. Like the random approach, there is little intelligence in the selection of the constituent devices needed for the farm with respect to bandwidth efficiency. Accordingly, farms constructed using the first-come-first-served paradigm for device selection may also result in bandwidth inefficiency and performance degradation. Another extreme is an exhaustive algorithm, which explores every possible permutation of devices in order to pick the optimum set. Unfortunately, this can take an unacceptable amount of time, and the algorithm becomes infeasible for even moderate sized problems.
In view of the foregoing, there are desired improved methods and apparatus for selecting constituent devices needed for a farm from the pool of available devices in a tree hierarchy so that the resultant farm would employ bandwidth more efficiently than achievable using the other approaches.